1913D - Array Collapse - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f;
ll n,mod=998244353;
ll p[300010];
ll q[300010];
ll f[300010];
ll l[300010]; 
ll s[300010];
void init() {
	for(int i=1;i<=n+1;i++) p[i]=q[i]=f[i]=l[i]=s[i]=0;
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>n;
		init();
		for(int i=1;i<=n;i++) cin>>p[i];
		l[1]=0,p[n+1]=2e16;
		for(int i=2;i<=n+1;i++) {
			int x=i-1;
			while(x&&p[x]>=p[i]) x=l[x];
			l[i]=x;
		}
		f[0]=q[0]=s[0]=1;
		for(int i=1;i<=n+1;i++) {
			f[i]=((s[i-1]-s[l[i]]+q[l[i]])%mod+mod)%mod;
			if(l[i]) q[i]=(f[i]+q[l[i]])%mod;
			else q[i]=f[i];
			s[i]=(s[i-1]+f[i])%mod;
		}
//		for(int i=1;i<=n;i++) cout<<f[i]<<' ';
//		cout<<endl;
		cout<<f[n+1]<<'\n';
	} 
    return 0;
}